#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> hash;
        int ma = 0;
        char mi = 0;
        for (auto i : s)
            if (ma < ++hash[i]) ma = hash[i], mi = i;
        int n = s.size();
        if (ma > (n + 1) / 2) return "";
        string ret = s;
        int i = 0;
        while (hash[mi]--) ret[i] = mi, i += 2;
        for (auto& [x, y] : hash)
        {
            while (y-- > 0) {
                if (i >= n) i = 1;
                ret[i] = x, i += 2;
            }
        }
        return ret;
    }
};